package javax;

public class java_3_12 {
    public static void main(String[] args){
        int[] arr = {1,3,4,2,5};

        for (int i=0;i<arr.length;i++){
            heapInsert(arr,i);
        }
        for (int obj :arr){

            System.out.println(obj);
        }
        heapSort(arr);
       /* for (int obj :arr){

            System.out.println(obj);
        }*/
    }
    public static void heapSort(int[] arr){
        if (null == arr|| arr.length<2){
            return;
        }
        for (int i =0 ;i<arr.length;i++){
            heapInsert(arr,i);
        }
        int heapSize = arr.length;
        swap(arr,0,heapSize);
        while (heapSize>0){
            heapify(arr,0,heapSize);
            swap(arr,0,--heapSize);
        }
    }
    //建立大根堆
    public static void heapInsert(int[] arr,int index){
       if ( arr[index] > arr[(index-1)/2]){
           swap(arr,index,(index-1)/2);
           index = (index-1)/2;
       }
    }
    //进行一次调整
    public static void heapify(int[] arr,int heapSize,int index){
        int left = index * 2+1;
        while (left<heapSize){
            int largest = left+1<heapSize && arr[left]> arr[left+1]?left:left+1;
            largest = arr[largest]>arr[index]?largest:index;
            if (largest==index){
                break;
            }
            largest = index;
            index = index*2 +1;
        }
    }
    //交换
    public static void swap(int[] arr,int i,int j){
        int obj = arr[i];
        arr[i] = arr[j];
        arr[j] = obj;
    }
}
